#include<bits/stdc++.h>
using namespace std;
// 优化前：时间打败了 10% 的用户
// class Solution {
// public:
//     map<int, int> mp;
//     bool containsNearbyDuplicate(vector<int>& nums, int k) {
//         for(int i = 0; i < nums.size(); i++){
//             if(mp.find(nums[i]) != mp.end() && i - mp[nums[i]] <= k){
//                 return true;
//             }
//             mp[nums[i]] = i;
//         }
//         return false;
//     }
// };

//优化后：
    class Solution {
    public:
        unordered_set<int> st;
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            for(int i = 0; i < nums.size(); i++){
                if(i > k)st.erase(nums[i - k - 1]);
                if(st.count(nums[i]))return true;
                st.emplace(nums[i]);
            }
            return false;
        }
    };

/**
 * 2022.1.19
 * 滑动窗口超过 94 %
 */